package DataStructure.hash;

import java.util.*;

/**
 * 146. LRU 缓存 https://leetcode.cn/problems/lru-cache
 */
public class LRUCache {

    private final LinkedHashMap<Integer, Integer> map;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        //1、选用可设置accessOrder的构造函数
        //2、重写removeEldestEntry()方法，在插入元素后若size大于容量，则返回true，移除最长时间没被访问的元素
        map = new LinkedHashMap<Integer, Integer>((int) (capacity/0.75) + 1, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}

//方法2：直接继承LinkedHashMap实现，但是这样写还暴露了其它不必要的方法，破坏了LRUCache的封装性
class LRUCache2 extends LinkedHashMap<Integer, Integer> {

    private final int capacity;

    public LRUCache2(int capacity) {
        super((int) (capacity/0.75) + 1, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    //重写removeEldestEntry()方法，在插入元素后若size大于容量，则返回true，移除最长时间没被访问的元素
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
}

//方法3：用HashMap和双向链表实现
class LRUCache3 {

    private final HashMap<Integer, Node> map;
    private final int capacity;
    Node head = new Node(), tail = new Node();

    public LRUCache3(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>((int) (capacity/0.75) + 1);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        Node node = map.getOrDefault(key, null);
        if (node == null) return -1;
        afterNodeAccess(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node(key, value);
            moveToTail(node);
        } else {
            node.val = value;
            afterNodeAccess(node);
        }
        map.put(key, node);
        afterNodeInsert();
    }

    private void moveToTail(Node node) {
        node.pre = tail.pre;
        node.next = tail;
        node.pre.next = node;
        tail.pre = node;
    }

    private void afterNodeAccess(Node node) {
        if (tail.pre != node) { //node被访问后，要从链表移除然后添加到尾部
            node.pre.next = node.next;
            node.next.pre = node.pre;
            moveToTail(node);
        }
    }

    private void afterNodeInsert() {
        if (map.size() > capacity) { //超出容量则从map和链表中移除链头元素
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.pre = head;
        }
    }

    static class Node { //node节点中需要存储key-value，以及前后指针
        Node pre, next;
        int key;
        int val;
        Node(){}
        Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
}

//方法4：使用HashMap和LinkedList实现，这种方法问题在于移动LinkedList中指定元素时需要先查找元素位置，时间复杂度O(n)
//class LRUCache4 {
//
//    private final HashMap<Integer, Integer> map;
//    private final int capacity;
//    private final LinkedList<Integer> linkedList;
//
//    public LRUCache4(int capacity) {
//        this.capacity = capacity;
//        map = new HashMap<>((int) (capacity/0.75) + 1);
//        linkedList = new LinkedList<>();
//    }
//
//    public int get(int key) {
//        Integer value = map.getOrDefault(key, null);
//        if (value == null) return -1;
//        moveToLast(key);
//        return value;
//    }
//
//    public void put(int key, int value) {
//        if (map.get(key) == null) {
//            linkedList.add(key);
//        } else {
//            moveToLast(key);
//        }
//        map.put(key, value);
//        if (map.size() > capacity)
//            removeEldestNode();
//    }
//
//    private void moveToLast(Integer key) {
//        if (!key.equals(linkedList.getLast())) {
//            linkedList.remove(key);
//            linkedList.add(key);
//        }
//    }
//
//    private void removeEldestNode() {
//        Integer first = linkedList.getFirst();
//        map.remove(first);
//        linkedList.removeFirst();
//    }
//}